/**
 * @author : HESS MArjorie, THUILLIER Jules, G4 - CIP2
 */
package ArbreBinaire;

import linkTreeInterface.Word;

/*
 * Cette classe générique représente les arbres binaires dont les noeuds
 * sont chaînés. En plus des méthodes de base, estVide, valeur, sag et sad,
 * elle définit les méthodes hauteur, écrire et estMiroir et créerMiroir.
 *
 *
 */
public class ArbreBinaireChaine<T> implements ArbreBinaire<T> {
	public static final ArbreBinaire arbreVide = new ArbreBinaireChaine();
	public T racine;
	public T valeur;
	public ArbreBinaire<T> sag;

	public ArbreBinaire<T> sad;
	
	// uniquement pour construire la constante arbreVide
	public ArbreBinaireChaine() {
	        sag = sad = null;
	}
	
	/**
     * Rôle : créer une feuille de l’arbre
     *        étiquetée par valeur
     */
	
	public ArbreBinaireChaine(T valeur) {
		this.valeur = valeur;
		this.sag = this.sad = (ArbreBinaireChaine<T>) arbreVide;
	}
	
	/**
     * Rôle : créer un noeud de l’arbre étiqueté par valeur et dont
     *        les sous−arbres sont sag et sad
     */
	
	public ArbreBinaireChaine(T valeur, ArbreBinaire<T> sag, ArbreBinaire<T> sad) {
	        this.valeur = valeur;
	        this.sag = (sag == null) ? arbreVide : sag;
	        this.sad = (sad == null) ? arbreVide : sad;
	}
	
	/**
	* Rôle : retourne true si l’arbre courant est vide
	*        et false sinon
	*/
	
	public boolean estVide() { 
		return this == arbreVide;
	}
	/**
	 * Rôle : retourne true si l’arbre courant est une feuille
	 *        et false sinon
	 */
	
	public boolean estUneFeuille() throws ArbreVideException { 
		return this.sag() == arbreVide && this.sad() == arbreVide;
	}

	
	/**
	 * Rôle : retourne le sous−arbre gauche de l’arbre courant
	 */
	
	public ArbreBinaire<T> sag() throws ArbreVideException { 
		if (estVide())
			throw new ArbreVideException();
		return this.sag;
	}
	
	/**
	 * Rôle : retourne le sous−arbre droit de  l’arbre courant
	 */
	
	public ArbreBinaire<T> sad() throws ArbreVideException { 
		if (estVide()) 
			throw new ArbreVideException();
		return this.sad;
	}
	
	/**
	 * Rôle : modifie le sous−arbre gauche de l’arbre courant
	 */
	
	public void changerSag(ArbreBinaire<T> g) { 
		this.sag = g;
	}
	
	/**
	 * Rôle : modifie le sous−arbre droit de l’arbre courant
	 */
	
	public void changerSad(ArbreBinaire<T> d) {
		this.sad = d;
	}

	/**
	 * Rôle : retourne la valeur de l’arbre courant
	 */
	
	public T valeur() throws ArbreVideException { 
		if (estVide()) 
			throw new ArbreVideException(); 
		return this.valeur; 
	}
	
	public void valeur(T a) {
		this.valeur = a;	
	}
	  
	
	  
	/**
	   * Rôle : écrit sur la sortie standard l’arbre courant. Il est écrit
	   * de façon horizontale avec la racine placé à gauche.
	   *
	   * Note : utilise un parcours DNG
	   */
	
	public void ecrireArbre(String d) throws ArbreVideException {
	      ecrireArbre(this, d);
	}
	
	private void ecrireArbre(ArbreBinaire<T> a, String d) throws ArbreVideException{
		final String h = " "; 
		if (! a.estVide()) {
	          // écrire le sous arbre droit
	          ecrireArbre(a.sad(), d+h);
	          // écrire la valeur du noeud avec son décalage
	          System.out.println(d + a.valeur());
	          // écrire le sous arbre gauche
	          ecrireArbre(a.sag(), d+h);
	     }
	}
	
	
	private int hauteur(ArbreBinaire<T> a) throws ArbreVideException {
		return a.estVide() ? 0 :
			//sinon il existe au moins un sous−arbre
			1 + Math.max(hauteur(a.sag()),hauteur(a.sad()));
	}
	
	/** Rôle : retourne la hauteur de l’arbre binaire courant
	*
	* @return <code>int</code>
	*/
	public int hauteur() throws ArbreVideException { 
		if (estVide())
			throw new ArbreVideException(); 
		return hauteur(this)-1;
	}
	 /**
	  * Rôle : retourne un arbre binaire miroir de this
	  */
	public ArbreBinaire<T> creerMiroir() throws ArbreVideException { 
		return creerMiroir(this);
	}
		
	private ArbreBinaire<T> creerMiroir(ArbreBinaire<T> a) throws ArbreVideException {
		return a.estVide() ? arbreVide :new ArbreBinaireChaine<T>(a.valeur(),creerMiroir(a.sad()), creerMiroir(a.sag()));
	}
	/**
	 * Rôle : retourne vrai si les arbres this et a sont miroirs
	 *        et faux sinon
	 */
		
	public boolean estMiroir(ArbreBinaire<T> a) throws ArbreVideException {
		return estMiroir(this,a);
	}

	private boolean estMiroir(ArbreBinaire<T> a, ArbreBinaire<T> b) throws ArbreVideException{
		if (a.estVide() && b.estVide())
		    // les deux arbres sont vides
			return true;
		if (a.estVide() || b.estVide())
		     // un des deux arbres est vide et pas l’autre
			return false;
			// les 2 arbres de sont pas vides
		if (!(a.valeur()).equals(b.valeur()))
			return false;
			// les 2 noeuds sont identiques
		return estMiroir(a.sag(),b.sad()) && estMiroir(a.sad(),b.sag());
	}
	
	/**
	 * Rôle : retourne vrai si l’arbre courant (this) est complet
	 *        et faux sinon. Note  un arbre vide est complet.
	 *
	 */
	public boolean estComplet() throws ArbreVideException { 
		return estVide() ? true : estComplet(this); 
	}
	
	/**
	 * Rôle : retourne vrai si l’arbre a complet
	 *        et faux sinon
	 * Antécédent : a non vide
	 */
		
	private boolean estComplet(ArbreBinaire<T> a) throws ArbreVideException {
		assert !a.estVide();
		if (a.sag().estVide() && a.sad().estVide()) return true; 
		return a.sag().estVide() || a.sad().estVide() ?
			// un des deux arbres est vide et pas l’autre
			false :
			// les 2 sous−arbres ne sont pas vides => poursuivre le test
			a.sag().estComplet() && a.sad().estComplet();
	}
	                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              

	@Override
	public String findTrad(ArbreBinaire<Word> sad, String mot) {
		// TODO Auto-generated method stub
		return null;
	}

	

		
	
	

}